Now that we've established the distinction between sparse and dense graphs, let's consolidate everything into a final head-to-head comparison. The choice between Prim's algorithm implementations is a classic engineering trade-off between simplicity and performance.

The core differences come down to two key decisions:

  • How the graph itself is represented (Adjacency Matrix vs. Adjacency List).
  • How the next minimum-weight edge is found (a simple array scan vs. an efficient Priority Queue).

The pseudo-code below highlights the main loop of each approach, revealing where the complexity differences arise.

Implementation 1: Simple Array Scan - O(V²)
while MST does not have V vertices:
  // Find minimum weight edge from an MST vertex
  // to a non-MST vertex. This is the bottleneck.
  min_edge = infinity
  next_vertex = null

  for each vertex u in MST:
    for each vertex v not in MST:
      if weight(u, v) < min_edge:
        min_edge = weight(u, v)
        next_vertex = v
  
  Add next_vertex to MST
Implementation 2: Priority Queue - O(E log V)
// PQ stores {weight, vertex}
PQ.insert({0, start_vertex})

while PQ is not empty:
  // Get next closest vertex efficiently
  {weight, u} = PQ.extract_min()

  if u is visited, continue

  Add u to MST
  Mark u as visited

  for each neighbor v of u:
    if v is not visited and weight(u,v) < dist[v]:
      dist[v] = weight(u, v)
      PQ.insert({dist[v], v})